using SharpGraphT.Event;
using SharpGraphT.Graph;
using SharpGraphT.Sharp.Sharp.Util;
using SharpGraphT.Traverse;

namespace SharpGraphT.Alg.Connectivity;

public class ConnectivityInspector<TV, TE> where TE : class, new() {
    private IList<ISet<TV>> _connectedSets;
    private IDictionary<TV, ISet<TV>> _vertexToConnectedSet;
    private IGraph<TV, TE> _graph;

    public ConnectivityInspector(IGraph<TV, TE> g) {
        Init();
        _graph = Objects.RequireNonNull(g);
        if (g.Type.IsDirected) {
            _graph = new AsUnmodifiableGraph<TV, TE>(g);
        }
    }

    public bool IsConnected => LazyFindConnectedSets().Count == 1;

    public ISet<TV> ConnectedSetOf(TV vertex) {
        if (_vertexToConnectedSet.TryGetValue(vertex, out var connectedSet)) {
            return connectedSet;
        }

        connectedSet = new HashSet<TV>();

        var i = new BreadthFirstIterator<TV, TE>(_graph, vertex);

        while (i.MoveNext()) {
            connectedSet.Add(i.Current);
        }

        _vertexToConnectedSet[vertex] = connectedSet;

        return connectedSet;
    }

    public IList<ISet<TV>> ConnectedSets => LazyFindConnectedSets();

    private void GraphOnEdgeAdded(object? sender,
        GraphEdgeChangeEventArgs<TV, TE> e) {
        var source = e.EdgeSource;
        var target = e.EdgeTarget;
        var sourceSet = ConnectedSetOf(source);
        var targetSet = ConnectedSetOf(target);

        if (sourceSet == targetSet) {
            return;
        }

        var merge = sourceSet.Union(targetSet).ToHashSet();
        _connectedSets.Remove(sourceSet);
        _connectedSets.Remove(targetSet);
        _connectedSets.Add(merge);
        foreach (var v in merge) {
            _vertexToConnectedSet[v] = merge;
        }
    }

    private void GraphOnEdgeRemoved(object? sender,
        GraphEdgeChangeEventArgs<TV, TE> e) =>
        Init();

    public bool PathExists(TV sourceVertex, TV targetVertex) =>
        ConnectedSetOf(sourceVertex).Contains(targetVertex);

    public void Listen(IListenableGraph<TV, TE> graph) {
        graph.EdgeAdded += GraphOnEdgeAdded;
        graph.EdgeRemoved += GraphOnEdgeRemoved;
        graph.VertexAdded += GraphOnVertexAdded;
        graph.VertexRemoved += GraphOnVertexRemoved;
    }

    private void GraphOnVertexAdded(object? sender,
        GraphVertexChangeEventArgs<TV> e) {
        var component = new HashSet<TV>();
        component.Add(e.Vertex);
        _connectedSets.Add(component);
        _vertexToConnectedSet[e.Vertex] = component;
    }

    private void GraphOnVertexRemoved(object? sender,
        GraphVertexChangeEventArgs<TV> e) =>
        Init();

    private void Init() {
        _connectedSets = null;
        _vertexToConnectedSet = new Dictionary<TV, ISet<TV>>();
    }

    private IList<ISet<TV>> LazyFindConnectedSets() {
        if (_connectedSets != null) {
            return _connectedSets;
        }

        _connectedSets = new List<ISet<TV>>();
        var vertexSet = _graph.VertexSet;

        if (!vertexSet.Any()) {
            return _connectedSets;
        }

        var i = new BreadthFirstIterator<TV, TE>(_graph);
        new MyTraversalListener(this, i);

        while (i.MoveNext()) { }

        return _connectedSets;
    }

    private class MyTraversalListener {
        private ISet<TV> _currentConnectedSet;

        private ConnectivityInspector<TV, TE> _inspector;

        public MyTraversalListener(ConnectivityInspector<TV, TE> inspector,
            BreadthFirstIterator<TV, TE> iterator) {
            _inspector = inspector;
            iterator.ConnectedComponentFinished +=
                IteratorOnConnectedComponentFinished;
            iterator.ConnectedComponentStarted +=
                IteratorOnConnectedComponentStarted;
            iterator.VertexTraversed += IteratorOnVertexTraversed;
        }

        private void IteratorOnConnectedComponentFinished(object sender,
            ConnectedComponentTraversalEventArgs e) =>
            _inspector._connectedSets.Add(_currentConnectedSet);

        private void IteratorOnConnectedComponentStarted(object sender,
            ConnectedComponentTraversalEventArgs e) =>
            _currentConnectedSet = new HashSet<TV>();

        private void IteratorOnVertexTraversed(object sender,
            VertexTraversalEventArgs<TV> e) {
            var v = e.Vertex;
            _currentConnectedSet.Add(v);
            _inspector._vertexToConnectedSet[v] = _currentConnectedSet;
        }
    }
}